package com.gxc.string;

/**
 * 给定一个字符串str，返回把str全部切成回文子串的最小分割数。
 * [举例]
 * str="ABA"。
 * 不需要切割，str本身就是回文串，所以返回0。
 * str="ACDCDCDAD"。
 * 最少需要切2次变成3个回文子串，比如“A”、“CDCDC”和”DAD”，所以返回2。
 *
 * 解法：
 * 题目求解字符串的最长回文子串
 * 得到dp[i][j] 即可得到每个位置能够构成回文子串的最大长度
 * 然后从0 开始遍历取  dp[0][j] 的最大值，如果为0，则单个为一组
 *
 */
public class PalindromicCutting {

    public static void main(String[] args) {
        String str = "ABA";
        System.out.println(isPalindrome(str.toCharArray()));
        System.out.println(process(str));

        str = "ACDCDCDAD";
        System.out.println(isPalindrome(str.toCharArray()));
        System.out.println(process(str));
    }

    public static int process(String str) {
        char[] chars = str.toCharArray();
        boolean palindrome = isPalindrome(chars);
        //如果本身是回文则返回0
        if (palindrome) return 0;

        int l = str.length();
        boolean[][] dp = new boolean[l][l];

        for (int j = 0; j < l; j++) {
            for (int i = j; i >= 0; i--) {
                if (i == j) {
                    dp[i][j] = true;
                } else if (chars[i] == chars[j]){
                    if (i+1 == j) dp[i][j] = true;
                    else {
                        dp[i][j] =  dp[i+1][j-1];
                    }
                }
            }
        }

        //计算以每个字符为开头的最大回文
        int time = 0;
        int i = 0;
        while (i < l) {
            int j = chars.length-1;
            //i 位置 倒序查看最长的回文位置，最终是自己
            while (!dp[i][j]) {
                j--;
            }
            time++;
            if (j>i) i = j;
            i++;
        }

        return time;
    }

    private static boolean isPalindrome(char[] chars) {
        int s = 0;
        int e = chars.length-1;
        while (s <= e) {
            if (chars[s] != chars[e]) return false;
            else {
                s++;
                e--;
            }
        }
        return true;
    }
}
